package com.zet.algorithm;

/**
 * 快速排序算法
 *
 * 快速排序的时间复杂度：快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。这句话很好理解：
 * 假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。

 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，
 而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。

 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

 快速排序的稳定性：快速排序是不稳定的算法，它不满足稳定算法的定义；所谓算法稳定性指的是对于一个数列中的两个相等的数a[i]=a[j]，
 在排序前,a[i]在a[j]前面，经过排序后a[i]仍然在a[j]前，那么这个排序算法是稳定的

 * @Author: zet
 * @Date: 2018-03-24 12:10
 */
public class QuikSort {

    /**
     * 排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr){
        return quikSort(arr, 0, arr.length -1);
    }

    /**
     * 排序
     * @param arr 待排序的数组
     * @return 有序数组
     */
    private static int[] quikSort(int[] arr,int left,int right){
        int _left = left;
        int _right = right;

        int base = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= base) {
                right --;
            }
            arr[left] = arr[right];

            while (left < right && arr[left] <= base) {
                left ++;
            }
            arr[right] =arr[left];

            arr[left] = base;
            quikSort(arr, _left, left - 1);
            quikSort(arr, left+1,_right);
        }

        return arr;
    }
}
